package digui;

public class _03排序的递归形式 {
    public static void main(String[] args) {
        int[] arr =utils.Utils.getRandomArr(10,1,20);
        for (int i = 0 ; i < arr.length;i++){
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        sort(arr);
        for (int i = 0; i <arr.length ; i++){
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        System.out.println("niXu:" + niXu);
    }

    //插入排序
    static void insertSort(int[] a ,int i){
        if (i == 0 ){
            return ;
        }
        //对前n-1个元素进行排列
        insertSort(a,i-1);
        //将剩下的一个元素归位，完成全部元素排列
        int x = a[i];
        int index = i-1;
        while(index > -1 && a[index] > x){
            a[index+1] = a[index];
            index --;
        }
        a[index+1] =x ;
    }

    //希尔排序
    public static void shellSort(int[] arr){
        //不断缩小增量
        for (int interval = arr.length / 2 ; interval > 0; interval = interval/2){
            //增量为interval的插入排序
            for (int i = interval ; i < arr.length ; i = i++){
                int target = arr[i];
                int index = i-interval;
                while (index > -1 && arr[index] >target){
                    arr[index + interval ] = arr[index];
                    index -= interval;
                }
                arr[index + interval] = target;
            }
        }
    }

    //快速排序(单向、双向指针扫描）
    public static void quickSort(int[] a,int p,int r){
        if (p<r){
            int q = partition(a,p,r);
            quickSort(a,p,q-1);
            quickSort(a,q+1,r);
        }
    }
    //单向指针扫描快速排序确定分界点（左边元素小于分界，右边元素大于分界）
    public static int partition(int [] a,int p,int r){
        int pivot = a[p];  //主元
        int sp = p+1;  //扫描指针
        int bigger = r;//右侧指针
        while (sp <= bigger){
            if (a[sp] <= pivot){   //扫描元素小于主元，左指针向右移
                sp ++;
            }else { //扫描元素大于主元，二指针元素交换，右指针左移
                swap(a,sp,bigger);
                bigger--;
            }
        }
        swap(a,p,bigger);  //交换主元和右指针位置，此时主元位置就是分界点
        return bigger;
    }

    //双向指针扫描快速排序确定分界点
    public static int partition1(int[] a,int p ,int r){
        int pivot = a[p];
        int left = p+1;
        int right = r;
        while (left<=right){
            //left不停往左走，直到遇见大于主元素的元素
            while (left<=right&&a[left] <= pivot) left++;//循环退出时，left一定是指向第一个大于主元的位置
            while (left<=right&&a[right] > pivot) right--;//循环结束时，right一定是指向第一个小于主元的位置
            if (left< right){
                swap(a,left,right);
            }
        }
        //while循环退出时，两者交错，且right指向的是最后一个小于等于主元的元素，也就是主元应该呆的位置
        swap(a,p,right);
        return right;
    }

    //三向扫描法快速排序确定分界点（在左、中、右三点中确定中值，尽量保持中值点在中间）
    public static int partition2(int[] a,int p ,int r){
        //在p，mid，r三个值中寻找中值
        int midIndex = p + ((r-p)>>1);//中间下标
        int midValueIndex = -1;//中值下标
        if (a[p] <= a[midIndex] && a[p] >= a[r]){
            //p是中值
            midValueIndex =p;
        }else if(a[r] <a [p] && a[r] > a[midIndex]){
            //r是中值
            midValueIndex = r;
        }else {
            midValueIndex = midIndex;
        }
        swap(a,p,midValueIndex);
        int pivot = a[p];
        int left = p+1;
        int right = r;
        while (left<=right){
            //left不停往左走，直到遇见大于主元素的元素
            while (left<=right&&a[left] <= pivot) left++;//循环退出时，left一定是指向第一个大于主元的位置
            while (left<=right&&a[right] > pivot) right--;//循环结束时，right一定是指向第一个小于主元的位置
            if (left< right){
                swap(a,left,right);
            }
        }
        //while循环退出时，两者交错，且right指向的是最后一个小于等于主元的元素，也就是主元应该呆的位置
        swap(a,p,right);
        return right;
    }



    //归并排序（分割为左右两个数组后分别排序再进行合并
    static int[] helper;
    public static void sort(int[] arr) {
        helper = new int[arr.length];
        sort1(arr, 0, arr.length - 1);
    }
      /*
  分成两段分别排序，然后再合并
  */

    private static void sort1(int[] A, int p, int r) {
        if (p < r) {
            int mid = p + ((r - p) >> 1);
            sort1(A, p, mid); //对左侧排序
            sort1(A, mid + 1, r);//对右侧排序
            merge(A, p, mid, r);//合并
        }
    }

    static int niXu = 0;
    /**
     *假设数组的两段分别有序，借助一个辅助数组来缓存原数组，用归并的思路将元素从辅助数组中拷贝回原数组
     *@param A 原数组
     *@param p 低位
     *@param mid 中间位
     *@param r 高位
     **/
    private static void merge(int[] A, int p, int mid, int r) {
        //拷贝到辅助空间的相同位置
        System.arraycopy(A, p, helper, p, r - p + 1);
        //辅助数组的两个指针
        int left = p, right = mid + 1;
        //原始数组的指针
        int current = p;
        while (left <= mid && right <= r) {
            if (helper[left] <= helper[right]) {
                A[current++] = helper[left++];
            } else { //右边小
                A[current++] = helper[right++];
                niXu += mid - left + 1;
            }
        }
        //  这样做完后，左边指针可能没到头;右边的没到头也没关系，想想为什么？
        while (left <= mid) {
            A[current] = helper[left];
            current++;
            left++;
        }
    }




    private static void swap(int[] a, int pivot, int i) {
        int temp = a[pivot];
        a[pivot] = a[i];
        a[i]= temp;
    }
}
